Bitwise operations in chess

Bitwise operations

Definition

In chess programming, bitwise operations are low-level CPU instructions (AND, OR, XOR, NOT, shifts, and related bit tricks) applied to 64-bit integers that represent the chessboard. Each bit corresponds to a square (usually a1 = bit 0 through h8 = bit 63). Manipulating these bits en masse allows an engine to compute moves, attacks, and features extremely quickly.

How it is used in chess

Most modern engines represent sets of squares as bitboards, one 64-bit value per piece type, color, or feature (e.g., all white pawns, all occupied squares, all squares attacked by knights, etc.). Bitwise operations on these bitboards enable:

• Move generation: Building legal or pseudo-legal moves by combining and masking attack sets.
• Attack detection: Finding checks, pins, and x-rays by sliding along rays and masking with occupancy.
• Evaluation features: Identifying passed pawns, outposts, open files, and king shelters using precomputed masks.
• Hashing and incremental updates: Using XOR to update Zobrist hashes when making/unmaking moves.
• Counting and scanning: Using popcount (count 1 bits) for material or mobility and bit scans to find specific squares.

Strategic and historical significance

Bitboard techniques and bitwise operations were pivotal in making engines both stronger and faster. Early programs often used array-based boards (e.g., 0x88 mailbox). As 64-bit CPUs became ubiquitous, bitboards became a natural fit: 64 squares map to 64 bits. This alignment enabled lightning-fast move generation and attack computation, a key contributor to the strength of engines such as Crafty, Stockfish, Komodo, and others.

Improvements like “magic bitboards” (fast indexing of sliding piece attacks) and later CPU instructions (POPCNT, LZCNT/BSF, and BMI2’s PEXT) further accelerated attack lookups. These optimizations helped engines search deeper and evaluate more accurately—part of the broader progress that led to milestones such as Kasparov vs. Deep Blue, 1997, and today’s superhuman analysis tools.

Core operations you’ll see

• AND (&): Intersect sets. Example: attacks AND enemy pieces = capture targets.
• OR (|): Union sets. Example: combine white pieces into one occupancy mask.
• XOR (^): Toggle bits. Example: unmake/make moves in Zobrist hashing or flipping occupancy on a move.
• NOT (~): Invert bits. Example: attacks AND ~ownPieces = exclude friendly-occupied squares.
• Shifts (<<, >>): Move sets north/south/east/west by bit offsets. Used heavily for pawn pushes and some attack generators (with file masks to prevent wrap-around).
• Popcount: Count 1-bits for material, mobility, or phase calculations.
• Bit scan forward/reverse: Find the first/last 1-bit to iterate pieces or attacks.
• Indexed attacks (magic/pext): Rapid sliding attacks by indexing precomputed tables using (occupancy AND rayMask) compressed via magic multipliers or PEXT.

Examples

Example 1: Knight attacks via masks
Put a white knight on d4. A precomputed mask KnightAttacks[d4] contains all potential target squares. Pseudo-legal moves are computed as:
KnightMoves = KnightAttacks[d4] AND ~WhitePieces; Captures = KnightAttacks[d4] AND BlackPieces.

Visualize the attack set:

Example 2: Pawn move generation with shifts

• White single push: (WhitePawns << 8) AND Empty.
• White double push from rank 2: ((WhitePawns << 8) AND Empty) << 8 AND Empty AND Rank4Mask.
• White captures:
  • NE capture: (WhitePawns << 9) AND ~FileAMask AND BlackPieces.
  • NW capture: (WhitePawns << 7) AND ~FileHMask AND BlackPieces.
• En passant: use the ep-square mask (EpMask) and the same shifted captures but AND EpMask.

These are set operations, so thousands of potential pawn moves can be considered in a handful of CPU instructions.

Example 3: Sliding attacks (rook/bishop/queen)
For a rook on d4, you first mask the rook’s rays (rank and file) with current occupancy to find blockers, then index a precomputed attack set. With “magic” or PEXT-based tables you do:
index = Compress(occupancy AND RookRayMask[d4]);
attacks = RookAttackTable[d4][index];
Legal moves = attacks AND ~WhitePieces; Captures = attacks AND BlackPieces.

Example 4: Zobrist hashing with XOR
When a white knight moves from g1 to f3 in a game starting 1. Nf3, the hash updates as:
hash ^= Z[WhiteKnight][g1]; // remove knight from g1
hash ^= Z[WhiteKnight][f3]; // add knight to f3
hash ^= Z[SideToMove]; // toggle side to move

Interesting facts

• Why 64-bit? A chessboard has 64 squares—perfect for a single 64-bit integer. On 32-bit systems, bitboards were emulated with pairs of 32-bit integers.
• “Magic bitboards” and later PEXT-driven attack tables dramatically cut the cost of rook/bishop attack generation, a historically expensive part of move generation.
• POPCNT and LZCNT/bit scan intrinsics let engines count and locate bits in a single instruction—great for evaluating mobility and material quickly.
• Many evaluation concepts—passed pawns, open files, outposts—are recognized with simple masks and a few AND/OR operations.

Usage notes and pitfalls (for implementers)

• Always mask files when shifting to avoid wrap-around (e.g., shifting east from the h-file must be masked out).
• Keep separate bitboards for color and piece types; maintain aggregate occupancy for fast checks like “is square empty?”.
• Prefer precomputed attack masks for knights and kings; use magic/pext for sliders to avoid branching.
• Incremental updates (XOR toggling bits, keeping phase/material counts) are faster than recomputing from scratch.

A quick on-board demonstration

Starting position. Think of White’s double pawn push on e4 as a two-step shift with masks to ensure both e3 and e4 are empty:

Why it matters for practical chess

Although humans don’t think in bits, our analysis tools do. The speed and precision of bitwise operations underpin the tactical sharpness and depth of modern engines. When your engine suggests a dazzling rook lift or finds a long forcing line, there’s a good chance fast bitboard operations helped it search and verify that idea efficiently.